package sword.offer;

import java.util.*;

/**
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class TwentyEight {
    /**
     * 这道题使用BFS层序遍历 将每层结点放到一个数组(最好用双端队列)，然后第一个和最后一个相同，
     * 第二个和倒数第二个相同 两两比较 ，都相同 则这一层符合对称
     * <p>
     * 基线条件：<br/>
     * 1. 队列中的数据两两不相同 或者 数量为奇数 则 return false<br/>
     * 2. 队列中的数据为空了 则 遍历完成 return true<br/>
     */
    class Solution1 {
        public boolean isSymmetric(TreeNode root) {
            if(Objects.isNull(root)){
                return true;
            }
            // 定义一个队列
            Queue<TreeNode> queue = new ArrayDeque<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                // arr这里的作用是拿到下一层的所有结点 包括null
                List<Integer> arr = new ArrayList<>();
                for (int i = queue.size(); i >0 ; i--) {
                    TreeNode node = queue.poll();
                    if (node.left != null){
                        queue.add(node.left);
                        arr.add(node.left.val);
                    }else{
                        arr.add(null);
                    }
                    if (node.right != null){
                        queue.add(node.right);
                        arr.add(node.right.val);
                    }else{
                        arr.add(null);
                    }
                }
                // 数量为奇数
                if (queue.size() % 2 != 0) {
                    return false;
                }
                // 两两不相同
                for (int i = 0; i < arr.size() / 2; i++){
                    if(!Objects.equals(arr.get(i), arr.get(arr.size() - i - 1))){
                        return false;
                    }
                }
            }
            return true;
        }
    }

    /**
     * 使用递归的方式，递归比较左右结点
     * 基线条件：<br/>
     * 1. 两个结点都为null 说明该条分支都遍历完了 true <br/>
     * 2. 只有其中一个结点都为null false <br/>
     * 3. 两个结点不相等 返回false <br/>
     * */
    class Solution2{
        public boolean isSymmetric(TreeNode root){
            if(root == null) return true;
            return recur(root.left,root.right);
        }

        public boolean recur(TreeNode lNode, TreeNode rNode){
            if(lNode == null && rNode ==null) return true;
            if(lNode == null || rNode == null) return false;
            if(lNode.val != rNode.val) return false;
            return recur(lNode.left,rNode.right) && recur(lNode.right,rNode.left);
        }
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
